import java.util.Arrays;

class Solution {
    public int maxDotProduct(int[] nums1, int[] nums2) {
        int n=nums1.length;
        int m=nums2.length;

        //状态表示：dp[i][j]，以0-i区间内nums1和0-j区间内nums2子序列的最大点积
        int[][] dp=new int[n+1][m+1];
        //初始化
        Arrays.fill(dp[0],-0x3f3f3f3f);
        for (int i = 0; i <= n; i++) {
            dp[i][0]=-0x3f3f3f3f;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                //状态转移方程
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
                dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]==-0x3f3f3f3f?0:dp[i-1][j-1]+nums1[i-1]*nums2[j-1]);
            }
        }

        return dp[n][m];
    }
}